The invention relates to the field of computer science, and more specifically, to a computerized system, a method, a program and a data storage medium for storing objects encrypted based on a key and providing for the deletion of the objects.
Secure data deletion often features as a requirement in a number of domains. As an example, privacy and data protection regulations of different countries have agreed on a set of common principles. Among those, “purpose” and “security” are particularly relevant, as it appears from Directive 95/46/EC of the European Parliament and of the Council of 24 Oct. 1995 on the protection of individuals with regard to the processing of personal data and on the free movement of such data, and from the OECD guidelines on the protection of privacy and transborder flows of personal data. The principle of “purpose” states that personal data can be stored only for purposes agreed by the data owner, and that once this purpose is no longer valid, data should be erased. Coupled with the security principle, that mandates that data should be kept secure from any potential abuses, it is clear that the legislator requires special care in the handling of “expired” data. Indeed, access to data whose purpose is expired would clearly represent a violation of both principles.
This is even truer when the information at hand belongs to particularly sensitive domains such as healthcare and finance. In this case, the numerous existing regulations require avoiding any unauthorized exposure of confidential corporate and government data by imposing fines and even civil and criminal liability. This is the case for example for the Health insurance portability and accountability act in 1996, the Financial services modernization act in 1999, the Public company accounting reform and investor protection act in 2002, and the Fair and accurate credit transactions act in 2003, of the US Congress.
Retaining data too long increases the risks of unwanted disclosure, for instance through a security breach or by subpoena. The truth of this statement is backed up by the number of incidents whereby companies have lost sensitive data. Such incidents are related in different news articles and studies, such as the ones by J. Vijayan entitled “Programmer who stole drive containing 1 million bank records gets 42 months”, Computer World, 2008, or by D. Sharp, entitled “Breach exposes 4.2 million credit, debit cards”, Associated Press, 2008, or by J. Evers, entitled “Credit card breach exposes 40 million accounts”, CNET News 2005. The 2010 annual study entitled “U.S. cost of a data breach” by Symantec Corporation in 2011 showed that the average cost of such a data breach is in the order of millions of dollars, and that this cost is rising over time.
These simple facts show how information that is no longer required can only become a liability for a company, and that an important goal of IT systems in the corporate world should be the ability of disposing of information in a secure way.
Standard OS deletion primitives do not offer a solution to the problem of secure deletion. Indeed, a deletion operation such as unlink( ) and remove( ) in Unix operating systems only remove the reference to a file from the filesystem data structure, leaving the actual data on the physical disk.
A first known approach towards secure file deletion is overwriting. However, if done naively, overwriting may still leave magnetic traces of past data in the disk. Gutmann et al. showed how secure deletion can be achieved by overwriting the content using certain patterns that are adapted to the low-level encoding mechanism of drives (P. Gutmaun, “Secure deletion of data from magnetic and solid-state memory”, in Proceedings of the 6th USENIX Security Symposium, pages 77-89, 1996). However, a number of problems affect this solution. Firstly, large files cannot be deleted efficiently. Secondly, if files are replicated to increase their availability, or backed up, the burden of deletion increases linearly in the number of copies.
In addition, tools that achieve secure deletion through data overwriting (like wipe, eraser and shred developed for known operating systems) work only if the overwrite patterns apply to the actual physical device at hand, if the patterns are actually being written to disk (and not only to cache), and if the writes are targeted to the disk sectors that contained the data. Without detailed knowledge of the media at hand, ensuring the first condition is hard. The second condition can be ensured in a complicated way, through an OS-level or disk-level write barrier, write cache flush, or by disabling the write cache. With respect to the third condition, enforcing write locality is quite hard in modern file system. Indeed, journaling file systems, such as, for instance, JFS, ReiserFS, XFS, Ext3, perform write operations on journals and not directly to disk. Other filesystems write redundant data, others take disk snapshots or cache data in temporary locations. Furthermore, it has been shown by M. Wei, L. M. Grupp, F. M. Spada, and S. Swanson in their paper entitled “Reliably erasing data from flash-based solid state drives”, in Proceedings of the 20th USENIX Security Symposium, 2011, that none of the available disk overwrite techniques are effective if data is stored on different media, such as solid-state drives. Generally, storage systems have many layers. The problem is that knowledge of lower-layer implementation mechanisms is lacking and the interfaces do not contain methods for instructing a lower layer to securely delete data.
A number of works have attempted to implement overwriting-based techniques as an automatic feature of existing filesystems. In the paper by Bauer and N. B. Priyantha entitled “Secure data deletion for linux file systems”, in Proceedings of the 10th conference on USENIX Security Symposium—Volume 10, SSYM'Ol, pages 12-12, Berkeley, Calif., USA, 2001, USENLX Association, the authors present an implementation of an overwrite-based secure deletion extension for the ext2 filesystem. The system is based on a separate daemon carrying out an asynchronous overwrite of blocks that have been marked as deleted. This work has the shortcoming of only supporting an outdated, non-journaled filesystem. In the papers by N. Joukov, H. Papaxenopoulos, and E. Zadok entitled “Secure deletion myths, issues, and solutions”, in Proceedings of the second ACM workshop on Storage security and survivability, StorageSS '06, pages 61-66, New York, N.Y., USA, 2006, ACM, and by N. Joukov and E. Zadok entitled “Adding secure deletion to your favorite file system”, in Proceedings of the Third IEEE International Security in Storage Workshop, pages 63-70, Washington, D.C., USA, 2005, IEEE Computer Society, the authors present a solution for secure deletion based on intercepting deletion calls and translating them with link( )/unlink( ) operations that move files in a specified folder. Then, the shred utility is asynchronously used on these files. All these works share the shortcomings of overwrite-based approaches highlighted above.
In their paper entitled “A revocable backup system”, in proceedings of the 6th conference on USENIX Security Symposium, Focusing on Applications of Cryptography—Volume 6, pages 9-9, Berkeley, Calif., USA, 1996, USENIX Association, D. Boneh and R. J. Lipton present an approach for deletion of content—in particular backed-up off-line content. The key idea the authors propose is to encrypt all the content that may require secure deletion, and—upon secure deletion request—carry out a deletion of the keys instead of the deletion of the file content. The authors also introduce the support for versioned backups. However, using such a system translates to the requirement of managing a number of cryptographic keys for each individual file.
The idea of leveraging on cryptography to achieve secure deletion has been picked up by a number of subsequent works. In the paper by Z. N. J. Peterson, R. Burns, J. Herring, A. Stubblefield, and A. D. Rubin entitled “Secure deletion for a versioning file system”, in proceedings of the 4th conference on USENIX Conference on File and Storage Technologies—Volume 4, pages 11-11, Berkeley, Calif., USA, 2005, USENIX Association, the authors present a solution to support secure deletion in a versioning filesystem, based on the idea of adding short, cryptographically computed tags to a file: the deletion of the tag implies the impossibility to recover the file. However, differently from keys, tags are public and can be stored and replicated as normal data.
In the paper entitled “The ephemerizer: making data disappear”, Technical report, Sun Microsystems, Inc., Mountain View, Calif., USA, 2005, Perlman presents the concept of the ephemerizer: a semi-trusted third party that creates and advertises public keys, and guarantees their secure deletion after a predefined amount of time. This way, users can encrypt the session keys used to encrypt messages for one another, using one of the keys of the ephemerizer, with the assurance that after their expiration time, these keys will no longer be available. In the paper entitled “File system design with assured delete”, in proceedings of the Third IEEE International Security in Storage Workshop, pages 83-88, Washington, D.C., USA, 2005, IEEE Computer Society, the same author presents a solution where such idea can be used to implement a filesystem. This work, however, pays the penalty of being built on a solution initially designed for encryption of messages between different users.
In the paper by R. Geambasu, T. Kohno, A. A. Levy, and H. M. Levy. entitled “Vanish: increasing data privacy with self-destructing data”, in proceedings of the 18th conference on USENIX security symposium, SSYM'09, pages 299-316, Berkeley, Calif., USA, 2009, USENIX Association, the authors show how the churn rate of DHT-based peer-to-peer systems can be used to achieve secure deletion. Their solution requires content to be encrypted using a cryptographic key, and such key needs to be split in shares using for instance Shamir's approach exposed in the paper by A. Shamir entitled “How to share a secret”, Commun. ACM, 22:612-613, November 1979. Then, the different shares of the key can be distributed to random users of a DHT. Since users will naturally disappear from the DHT, and given that keys are only stored in non-persistent memory, after a certain amount of time the key will no longer be available. However the scheme can be attacked by exploiting well-known sybil attacks on DHTs, as explained in the paper by Wolchok, Hofmann, Heninger, Felten, Halderman, Rossbach, Waters, and Witchel entitled “Defeating Vanish with low-cost Sybil attacks against large DHTh”, in proc. 17th Network and Distributed System Security Symposium (NDSS), ISOC, February 2010.
An approach, referred to as Di Crescenzo et al.'s approach that constitutes an approach for an abstraction of the secure deletion problem, is now presented. This approach is also described in the paper by Di Crescenzo, N. Ferguson, R. Impagliazzo, and M. Jakobsson entitled “How to forget a secret”, in proceedings of the 16th annual conference on Theoretical aspects of computer science, STACS'99, pages 500-509, Berlin, Heidelberg, 1999, Springer-Verlag. The method comprises building an erasable memory of arbitrary size from an external erasable memory of small, constant size and standard (non-erasable) memory of arbitrary size. The idea is centered around a key tree: each node of the tree is associated to a cryptographic key. No key is stored in plaintext in the tree, but it is stored after having been encrypted with the key associated to its parent node (encrypting a key being also called key-wrapping). The key associated to the root is stored in the external erasable memory, whereas the other values are stored in the standard memory. The key tree is a complete n-ary tree and the N=nm values that require secure deletion are arranged as leaves of this tree: the leaves are therefore the only nodes whose values are actual data and not cryptographic keys. The data associated to the leaves is encrypted using the key of each node's parent node. When a value requires secure deletion, the following operations are executed over the tree: for each node in the path between the node requiring deletion and the root, 1) a new value is drawn from the keyspace and is wrapped using the new unwrapped value of its ancestor; and 2) the value of each of its siblings is re-wrapped using the new unwrapped value of the ancestor. The same happens for the key associated to the root of the tree. In addition, since such key is stored on a securely erasable memory, its retrieval after the deletion operation is impossible. The node requiring secure deletion is not reencrypted. This way, its secure deletion is guaranteed since its decryption would require—thanks to the property of the tree—access to the old value of the root, which is no longer possible by definition, as it is stored in the erasable memory.
Thus, there is still a need for an improved method for storing data and providing for their later secure deletion.